package algorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Arrays;

public class ThreeSum {
    //还有继续优化的空间
    public static List<List<Integer>> threeSum(int[] nums) {

        //定义一个嵌套的列表来存储最终的结果
        List<List<Integer>> result = new ArrayList<>();

        // 1. 边界条件检查
        if (nums == null || nums.length < 3) {
            return result;
        }

        // 2. 排序 - 双指针的前提
        Arrays.sort(nums);

        // 3. 遍历数组，固定第一个数
        for (int i = 0; i < nums.length - 2; i++) {
            // 去重处理：跳过重复的固定值
            if (i != 0) {
                //第二个条件是防止面对极端情况数组发生越界
                while (nums[i] == nums[i - 1] && i < nums.length - 1) {
                    i++;
                }
            }

            // 4. 双指针寻找另外两个数
            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    // 找到满足条件的三元组
                    // 添加到结果中
                    result.add((Arrays.asList(nums[i], nums[left], nums[right])));
                    //移动指针
                    left++;
                    right--;
                    // 去重：移动指针跳过重复元素
                    //左端指针去重
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    //右端指针去重
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                    // 继续寻找其他可能的组合
                } else if (sum < 0) {
                    // 和太小，需要增大 - 移动左指针
                    left++;
                    while(left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }

                } else {
                    // 和太大，需要减小 - 移动右指针
                    right--;
                    while(left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
        }

        return result;

    }

    public static void main(String[] args) {
        int[] nums = new int[]{-1,0,1,2,-1,-4};
        List<List<Integer>> result = threeSum(nums);
        for (List<Integer> integerList : result) {
            System.out.print(integerList.toString() + " ");
        }

    }
}
